home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / utility.lha / utility / list.H < prev    next >
C/C++ Source or Header  |  1993-08-08  |  8KB  |  214 lines
  1. // This is a generic list package in C++.  Any kind of object can be the 
  2. // member of such a list, but specialized list types are normally created for
  3. // each type of object.  An element can be the member of many lists at a time.
  4. // Before an object is destructed, it must explicitly be taken out of any lists
  5. // (otherwise there will be pointers left pointing to deallocated space).
  6. //
  7. // .SS Derived list types
  8. // This is a protected class, i.e., it is not possible to create instances
  9. // of it.  Derived classes provide lists for specific types of objects.
  10. // First, a new list type must be declared, for example, a list of integers:
  11. //
  12. //    LIST_DECLARE(int);
  13. //    CONSTLIST_DECLARE(int);
  14. //
  15. // This declares a new class, called `intList', and a list of "const int".
  16. // List types should only be declared once, even if there are many lists.
  17. // After that, lists of this type can be declared as needed:
  18. //
  19. //    LIST(int) l1, l2;
  20. //    CONSTLIST(int) cl1;
  21. //
  22. // In every case where `Pointer' is a parameter in class GenericList, the
  23. // derived list types will accept either an object (int, above) or a
  24. // pointer to an object (int *, above).
  25. //
  26. // The function
  27. //
  28. //    LIST_DELETE(l,int);
  29. //
  30. // will delete all (integer) elements of the list `l', but not the list itself.
  31. // The elements had better be allocated on the free-store.
  32. //
  33. // .SS Performance
  34. // The list is implemented as an array of pointers.
  35. // Inserting elements at the front of the list (Insert() and operator +=)
  36. // is cheap; removing elements (except the first) and inserting at the end
  37. // is more expensive.  Assignment and passing a list as a VALUE parameter
  38. // requires copying of the pointer array, and is therefore expensive; pass
  39. // lists as "const reference" parameters instead.
  40. //
  41. // .SS History
  42. // Author: Dag Bruck
  43. //
  44. // $Id: list.H,v 1.2 91/03/03 22:08:14 dag Exp $
  45.  
  46. #ifndef LIST_H
  47. #define LIST_H
  48.  
  49.  
  50. #include <defs.H>
  51.  
  52.  
  53. typedef void* Pointer;
  54.  
  55.  
  56. class GenericList {
  57. friend class GenericIterator;
  58.   
  59. public:
  60.   GenericList();
  61.   // Constructs a list with no elements.
  62.  
  63.   ~GenericList();
  64.   // Destroys the list.  The elements in the list are not
  65.   // destroyed.  LIST_DELETE(list,type) will delete all
  66.   // elements of the list.
  67.  
  68.   void Insert(Pointer);
  69.   void operator += (Pointer);
  70.   // Inserts an element first in list.
  71.  
  72.   void Append(Pointer);
  73.   // Inserts an element last in list.  Not as efficient as Insert().
  74.  
  75.   void Append(const GenericList &);
  76.   // Appends another list to this list.
  77.  
  78.   void Remove(Pointer);
  79.   // Removes an element from the list. The element is not destroyed.
  80.   // It is o.k. to remove an element which is not a member of the list.
  81.  
  82.   void RemoveAll();
  83.   // Removes all elements from the list. The elements are not destroyed.
  84.  
  85.   boolean Member(Pointer) const;
  86.   // Returns true if the element is a member of list.
  87.  
  88.   void Replace(Pointer p, Pointer q);
  89.   // Replaces every occurence of "p" with "q".
  90.  
  91.   void Reverse();
  92.   // Reverses the order of the elements in the list.  The list is reversed
  93.   // in place, i.e., the original order is lost.
  94.   
  95.   Pointer First() const;
  96.   // Returns the first element of list, or nil if list is empty.
  97.  
  98.   Pointer Second() const;
  99.   // Returns the second element of list, or nil if < 2 elements exist.
  100.  
  101.   Pointer Third() const;
  102.   // Returns the third element of list, or nil if < 3 elements exist.
  103.  
  104.   Pointer Fourth() const;
  105.   // Returns the fourth element of list, or nil if < 4 elements exist.
  106.  
  107.   Pointer Fifth() const;
  108.   // Returns the fifth element of list, or nil if < 5 elements exist.
  109.  
  110.   Pointer Nth(const int) const;
  111.   // Returns the i:th element of list, or nil if < i elements exist.
  112.  
  113.   Pointer Last() const;
  114.   // Returns the last element of list, or nil if list is empty.
  115.  
  116.   unsigned Length() const;
  117.   // Returns the number of elements in list.
  118.  
  119.   boolean Empty() const;
  120.   // Returns true if list is empty.
  121.  
  122.   GenericList(const GenericList&);
  123.   // Used for passing parameters and return values.
  124.  
  125.   void operator = (const GenericList&);
  126.   // Assignment.
  127.  
  128. private:
  129.   Pointer* p;
  130.   // Array of pointers to actual member objects.
  131.  
  132.   unsigned n;
  133.   // Number of elements in list.
  134.  
  135.   unsigned size;
  136.   // Maximum number of elements in list.
  137.  
  138.   void Expand();
  139.   // Expand array of pointers to cope with more elements.
  140. };
  141.  
  142.  
  143. inline void GenericList :: operator += (Pointer e)
  144. { Insert(e); }
  145.  
  146. inline unsigned GenericList :: Length() const
  147. { return n; }
  148.  
  149. inline boolean GenericList :: Empty() const
  150. { return n == 0; }
  151.  
  152. #define LIST_DELETE(list,type) while (!(list).Empty()) \
  153. { type* p = (list).First(); (list).Remove(p); delete p; }
  154.  
  155. #define LIST(type)NAME2(type,List)
  156. #define CONSTLIST(type)NAME2(NAME2(const_,type),List)
  157. #define LIST_DECLARE(type)LIST_DECLARE2(LIST(type),type)
  158. #define CONSTLIST_DECLARE(type)CONSTLIST_DECLARE2(CONSTLIST(type),type)
  159. /* To make lists of nested classes we need some way to give full type */
  160. #define LIST_DECLARE2(__name,type) class __name : public GenericList { \
  161. public: \
  162. __name() {} \
  163. ~__name() {} \
  164. void Insert(type* x) { GenericList::Insert(x); } \
  165. void Insert(type& x) { GenericList::Insert(&x); } \
  166. void operator += (type* x) { GenericList::operator += (x); } \
  167. void operator += (type& x) { GenericList::operator += (&x); } \
  168. void Append(type* x) { GenericList::Append(x); } \
  169. void Append(type& x) { GenericList::Append(&x); } \
  170. void Append(const LIST(type)& x) { GenericList::Append(x); } \
  171. void Remove(type* x) { GenericList::Remove(x); } \
  172. void Remove(type& x) { GenericList::Remove(&x); } \
  173. boolean Member(type* x) const { return GenericList::Member(x); } \
  174. boolean Member(type& x) const { return GenericList::Member(&x); } \
  175. void Replace(type* p, type* q) { GenericList::Replace(p, q); } \
  176. void Replace(type& p, type& q) { GenericList::Replace(&p, &q); } \
  177. type* First() const { return (type *) GenericList::First(); } \
  178. type* Second() const { return (type *) GenericList::Second(); } \
  179. type* Third() const { return (type *) GenericList::Third(); } \
  180. type* Fourth() const { return (type *) GenericList::Fourth(); } \
  181. type* Fifth() const { return (type *) GenericList::Fifth(); } \
  182. type* Nth(const int i) const { return (type *) GenericList::Nth(i); } \
  183. type* Last() const { return (type *) GenericList::Last(); } \
  184. }
  185. #define CONSTLIST_DECLARE2(__name,type) class __name : public GenericList { \
  186. public: \
  187. __name() {} \
  188. __name(const LIST(type)& l) : GenericList(l) {} \
  189. ~__name() {} \
  190. void Insert(const type* x) { GenericList::Insert((type *) x); } \
  191. void Insert(const type& x) { GenericList::Insert((type *) &x); } \
  192. void operator += (const type* x) { GenericList::operator += ((type*)x); } \
  193. void operator += (const type& x) { GenericList::operator += ((type*)&x); } \
  194. void Append(const type* x) { GenericList::Append((type*)x); } \
  195. void Append(const type& x) { GenericList::Append((type*)&x); } \
  196. void Append(const CONSTLIST(type)& x) { GenericList::Append((LIST(type)&)x); } \
  197. void Remove(const type* x) { GenericList::Remove((type*)x); } \
  198. void Remove(const type& x) { GenericList::Remove((type*)&x); } \
  199. boolean Member(const type* x) const { return GenericList::Member((type*)x); } \
  200. boolean Member(const type& x) const { return GenericList::Member((type*)&x); } \
  201. void Replace(const type* p, const type* q) { GenericList::Replace((type*)p, (type*)q); } \
  202. void Replace(const type& p, const type& q) { GenericList::Replace((type*)&p, (type*)&q); } \
  203. const type* First() const { return (const type *) GenericList::First(); } \
  204. const type* Second() const { return (const type *) GenericList::Second(); } \
  205. const type* Third() const { return (const type *) GenericList::Third(); } \
  206. const type* Fourth() const { return (const type *) GenericList::Fourth(); } \
  207. const type* Fifth() const { return (const type *) GenericList::Fifth(); } \
  208. const type* Nth(const int i) const { return (const type *) GenericList::Nth(i); } \
  209. const type* Last() const { return (const type *) GenericList::Last(); } \
  210. }
  211.  
  212.  
  213. #endif
  214.